class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        // 假设[left, target]是合法区间
        while (left < right) {
            int mid = left + (right-left+1) / 2;
            if (nums[mid] > target) {
                right = mid-1;
            } else {
                left = mid;
            }
        }
        // 判断是否存在
        if (nums[left] == target) { // 实际存在
            return left;
        } else { // 不存在
            // 判断是插入左边还是右边位置
            if (nums[left] > target) {
                return left;
            } else {
                return left+1;
            }
        }
    }


    public int searchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        // 假设[target, right]是合法区间
        while (left < right) {
            int mid = left + (right-left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        // 判断是否存在
        if (nums[left] == target) {
            return left;
        } else {
            // 判断是插入左边还是右边位置
            if (nums[left] > target) {
                return left;
            } else {
                return left+1;
            }
        }
    }
}